package org.ala.linshen.dp;

/**
 * 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。
 *
 * 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。
 *
 * 有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。
 *
 * 为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。
 *
 * 返回确保骑士能够拯救到公主所需的最低初始健康点数。
 *
 * 注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
 * 输出：7
 * 解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
 * 示例 2：
 *
 * 输入：dungeon = [[0]]
 * 输出：1
 *
 *
 * 提示：
 *
 * m == dungeon.length
 * n == dungeon[i].length
 * 1 <= m, n <= 200
 * -1000 <= dungeon[i][j] <= 1000
 *
 * @author ala
 * @date 2024-09-20 14:16
 */
public class Q174 {

    public static void main(String[] args) {
        Q174 q = new Q174();

//        int[][] dungeon = {{-2,-3,3},{-5,-10,1},{10,30,-5}};
//        int[][] dungeon = {{0}};
        int[][] dungeon = {{-3, 5}};

        System.out.println(q.calculateMinimumHP(dungeon));
    }

    /**
     *  1）公主反向找到骑士，并且告诉骑士要携带多少生命点
     *  2）dp[i][j]表示从(i,j)点出发，到达右下时需要的最少生命点
     *      dp[i][j] = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
     *      如果 dp[i][j] < 1，说明该点是个补血点，dp[i][j] = 1
     *  3）dp[M - 1][N - 1] = -dungeon[M - 1][N - 1] + 1
     *  4）dp[0][0]即为答案
     */
    public int calculateMinimumHP(int[][] dungeon) {
        int M = dungeon.length, N = dungeon[0].length;

        int[][] dp = new int[M][N];
        //  初始时就携带1点血量（不能上来就噶了）
        dp[0][0] = 1;

        for (int i = M - 1 ; i >= 0 ; i--) {
            for (int j = N - 1 ; j >= 0 ; j--) {
                if (i == M - 1 && j == N - 1) {
                    dp[i][j] = -dungeon[i][j] + 1;
                    if (dp[i][j] < 1) {dp[i][j] = 1;}
                    continue;
                }

                int left = j < N - 1 ? dp[i][j + 1] : Integer.MAX_VALUE,
                    bottom = i < M - 1 ? dp[i + 1][j] : Integer.MAX_VALUE;
                dp[i][j] = Math.min(left, bottom) - dungeon[i][j];
                if (dp[i][j] < 1) { dp[i][j] = 1; }
            }
        }

        return dp[0][0];
    }
}
